import java.lang.reflect.Array;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:使用邻接矩阵来存储图
 * User: Gao zhao xu
 * Date: 2023-12-02
 * Time: 15:54
 */
public class GraphByMatrix {
    private char[] arrV;//顶点数组
    private int[][] matrix;//邻接矩阵数组
    private boolean isDirect;//判断是否是有向图

    /**
     * 此时
     *
     * @param size     ： 顶点个数
     * @param isDirect ： 是否为有向图
     */
    public GraphByMatrix(int size, boolean isDirect) {
        this.arrV = new char[size];
        this.matrix = new int[size][size];
        //初始化成最大值（以最大值代表无穷大）
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i], Constant.Max);
        }
        this.isDirect = isDirect;
    }

    /**
     * 顶点数组初始化
     */
    public void initArrV(char[] arrV) {
        for (int i = 0; i < arrV.length; i++) {
            this.arrV[i] = arrV[i];
        }
    }

    /**
     * 计算顶点的度
     *
     * @param v 顶点
     * @return 度数
     */
    public int getDevOfV(char v) {
        int indexV = getIndexOfV(v);
        if (indexV == -1) {
            System.out.println("没有顶点：" + v);
            return -1;
        }
        int dev = 0;
        //计算无向图：
        for (int i = 0; i < arrV.length; i++) {
            if (matrix[indexV][i] != Constant.Max) dev++;
        }
        //计算有向图还需要：
        if (isDirect) {
            for (int i = 0; i < arrV.length; i++) {
                if (matrix[i][indexV] != Constant.Max) dev++;
            }
        }
        return dev;
    }

    /**
     * 添加边
     *
     * @param srcV   开始顶点
     * @param destV  指向顶点
     * @param weight 权
     */
    public void addEdge(char srcV, char destV, int weight) {
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);
        if (srcIndex == -1) {
            System.out.println("没有顶点：" + srcV);
            return;
        } else if (destIndex == -1) {
            System.out.println("没有顶点：" + srcV);
            return;
        }

        matrix[srcIndex][destIndex] = weight;
        //判断是否为有向图
        if (!isDirect) matrix[destIndex][srcIndex] = weight;
    }

    /**
     * 获取v下标
     */
    public int getIndexOfV(char v) {
        for (int i = 0; i < this.arrV.length; i++) {
            if (v == arrV[i]) return i;
        }
        return -1;
    }

    /**
     * 打印邻接矩阵
     */
    public void printGraph() {
        System.out.print("  ");
        for (char x : this.arrV) {
            System.out.print(x + " ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            System.out.print(this.arrV[i] + " ");
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == Constant.Max) System.out.print("∞ ");
                else System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 广度优先遍历
     */
    public void bfs(char v) {
        boolean[] isOffer = new boolean[arrV.length];
        Queue<Integer> queue = new LinkedList<>();
        int srcIndex = getIndexOfV(v);
        if (srcIndex == -1) {
            System.out.println("没有顶点：" + v);
            return;
        }
        queue.offer(srcIndex);
        isOffer[srcIndex] = true;
        while (!queue.isEmpty()) {
            int top = queue.poll();
            for (int i = 0; i < matrix[top].length; i++) {
                if (matrix[top][i] != Constant.Max && !isOffer[i]) {
                    queue.offer(getIndexOfV(arrV[i]));
                    isOffer[i] = true;
                }
            }
            if (!queue.isEmpty()) System.out.print(arrV[top] + "(" + top + ")->");
            else System.out.print(arrV[top] + "(" + top + ")");
        }
        System.out.println();
    }

    /**
     * 深度优先遍历
     */
    //非递归
    public void dfs(char v) {
        boolean[] visited = new boolean[arrV.length];
        int vIndex = getIndexOfV(v);
        if (vIndex == -1) {
            System.out.println("没有顶点：" + v);
            return;
        }
        for (int i = 0; i < arrV.length; i++) {
            if (!visited[vIndex]) {
                System.out.print(arrV[vIndex] + " ");
                visited[vIndex] = true;
            }
            if (matrix[vIndex][i] != Constant.Max && !visited[i]) {
                vIndex = i;
                i = 0;
            }
        }
        System.out.println();
    }

    //递归
    public void dfsD(char v) {
        boolean[] visited = new boolean[arrV.length];
        int vIndex = getIndexOfV(v);
        if (vIndex == -1) {
            System.out.println("没有顶点：" + v);
            return;
        }
        dfsDChild(vIndex, visited);
        System.out.println();
    }

    public void dfsDChild(int srcIndex, boolean[] visited) {
        System.out.print(arrV[srcIndex] + " ");
        visited[srcIndex] = true;
        for (int i = 0; i < arrV.length; i++) {
            if (matrix[srcIndex][i] != Constant.Max && !visited[i]) {
                dfsDChild(i, visited);
            }
        }
    }

    static class Edge{
        public int srcIndex;
        public int destIndex;
        public int weight;

        public Edge(int srcIndex, int destIndex, int weight) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }
    /**
     * kruskal：克鲁斯卡尔算法求最小生成树，使用的是全局贪心算法
     * @param minTree 存储我们找到的边
     * @return 最小生成树的权值和
     */
    public int kruskal(GraphByMatrix minTree) {
        minTree.initArrV(arrV); //可以不用有
        //1.定义一个优先级队列，用于存储边
//        PriorityQueue<Edge> minHeap = new PriorityQueue<>(new Comparator<Edge>() {
//            @Override
//            public int compare(Edge o1, Edge o2) {
//                return o1.weight - o2.weight;
//            }
//        });
        PriorityQueue<Edge> minHeap = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        int n = arrV.length;
        //2.遍历邻接矩阵，把所有的边放到优先级队列中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j    < n; j++) {
                //无向图只需要遍历一半
                if (i < j && matrix[i][j] != Constant.Max) {
                    minHeap.offer(new Edge(i, j, matrix[i][j]));
                }
            }
        }
        int[] elem = new int[n];
        Arrays.fill(elem, -1);
        //3.开始从优先级队列中取边
        int size = 0;
        int totalWeight = 0;
        while (size < n - 1 && !minHeap.isEmpty()) {
            Edge edge = minHeap.poll();
            int srcIndex = edge.srcIndex;
            int destIndex = edge.destIndex;
            if (findRoot(elem,srcIndex) != findRoot(elem,destIndex)) {
                minTree.addEdgeForIndex(srcIndex, destIndex, edge.weight);
                System.out.println("第" + (size + 1) + "次选择的边：" + arrV[srcIndex] + "->" + arrV[destIndex]
                + " 权重为" + edge.weight);
                size++; //记录添加的边的条数
                union(elem, srcIndex, destIndex);
                totalWeight += edge.weight;
            }
        }
        if (size == n-1) return totalWeight;
        return -1; //没有最小生成树
    }
    //addEdge方法重写
    private void addEdgeForIndex (int srcIndex, int destIndex, int weight) {
        matrix[srcIndex][destIndex] = weight;
        //判断是否为有向图
        if (!isDirect) matrix[destIndex][srcIndex] = weight;
    }
    //并查集
    public  int findRoot (int[] elem, int x) {
        if (x < 0) throw new IndexOutOfBoundsException("下标不合法");
        while (elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }
    public  void union(int[] elem, int x1, int x2) {
        int x1Root = findRoot(elem, x1);
        int x2Root = findRoot(elem, x2);
        if (x1Root != x2Root) {
            if (x1Root > x2Root) {
                int tmp = x1Root;
                x1Root = x2Root;
                x2Root = tmp;
            }
            elem[x1Root] += elem[x2Root];
            elem[x2Root] = x1Root;
        }
    }

    /**
     * prime：普利姆算法求最小生成树，使用的是局部贪心算法
     * @param minTree 存储我们找到的边
     * @return 最小生成树的权值和
     */
    public int prime(GraphByMatrix minTree, char v) {
        minTree.initArrV(arrV); //可以不用有
        int srcIndex = getIndexOfV(v);
        //存储已经确定的点
        Set<Integer> setX = new HashSet<>();
        setX.add(srcIndex);
        //存储未确定的点
//        Set<Integer> setY = new HashSet<>();
//        for (int i = 0; i < arrV.length; i++) {
//            if (i != srcIndex)  setY.add(i);
//        }
        //需要一个优先级队列来存储边
        PriorityQueue<Edge> minHeap =  new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        for (int i = 0; i < arrV.length; i++) {
            if (matrix[srcIndex][i] != Constant.Max) {
                minHeap.offer(new Edge(srcIndex, i,matrix[srcIndex][i]));
            }
        }
        int size = 0;
        int totalWeight = 0;
        // 遍历优先级队列，选出n - 1 条边
        while (!minHeap.isEmpty()) {
            Edge min = minHeap.poll();
            int srcI = min.srcIndex;
            int destI = min.destIndex;
            if (setX.contains(destI)) {
                //构成环
                System.out.println("构成环的边：" + arrV[srcI] + "->" + arrV[destI] + " 权重为" + min.weight);
            }else {
                minTree.addEdgeForIndex(srcI, destI, matrix[srcI][destI]);
                System.out.println("第" + (size + 1) + "次选择的边：" + arrV[srcI] + "->" + arrV[destI]
                        + " 权重为" + min.weight);
                size++;
                totalWeight += min.weight;
                if (size == arrV.length - 1) return totalWeight;
                setX.add(destI);
//                setY.remove(destI);
                for (int i = 0; i < arrV.length; i++) {
                    if (matrix[destI][i] != Constant.Max && !setX.contains(i)) {
                        minHeap.offer(new Edge(destI, i,matrix[destI][i]));
                    }
                }
            }
        }
        return -1;
    }

    /**
     * dijkstra:迪杰克斯拉算法求最短路径,但是不能解决赋权图的问题
     * @param vSrc 指定的起点
     * @param dist 距离数组
     * @param pPath 路径
     * 时间复杂度：O(n^2)
     */
    public void dijkstra(char vSrc, int[] dist, int[] pPath) {
        int vIndex = getIndexOfV(vSrc);

        Arrays.fill(dist, Constant.Max);
        dist[vIndex] = 0;

        Arrays.fill(pPath, -1);
        pPath[vIndex] = 0;

        int n = arrV.length;
        boolean[] isUse = new boolean[n];

        for (int i = 0; i < n; i++) {
            int min = Constant.Max;
            int u = vIndex;
            for (int k = 0; k < n; k++) {
                if (!isUse[k] && min > dist[k]){
                    min = dist[k];
                    u = k;
                }
            }
            isUse[u] = true;
            for (int v = 0; v < n; v++) {
                if (!isUse[v] && matrix[u][v] != Constant.Max
                        && dist[v] > matrix[u][v] + dist[u]) {
                    dist[v] = matrix[u][v] + dist[u];
                    pPath[v] = u;
                }
            }
        }
    }
    public void printPath(char vSrc, int[] dist, int[] pPath) {
        int srcIndex = getIndexOfV(vSrc);
        int n = arrV.length;
        for (int i = 0; i < n; i++) {
            if (i != srcIndex) {
                ArrayList<Integer> path = new ArrayList<>();
                int pathI = i;
                while (pathI != srcIndex) {
                    path.add(pathI);
                    pathI = pPath[pathI];
                }
                path.add(srcIndex);
                Collections.reverse(path);
                System.out.print("最短路径:");
                for (int j = 0; j < path.size() - 1; j++) {
                    System.out.print(arrV[path.get(j)] + " -> ");
                }
                System.out.print(arrV[path.get(path.size() - 1)] + " 长度：" + dist[i]);
                System.out.println();
            }
        }
    }
    /**
     * BellmanFord:贝尔福德曼算法求最短路径,可以解决赋权图的问题(暴力解决)
     * @param vSrc 指定的起点
     * @param dist 距离数组
     * @param pPath 路径
     * 时间复杂度：O(n^2)
     */

    public boolean BellmanFord(char vSrc, int[] dist, int[] pPath) {
        int srcIndex = getIndexOfV(vSrc);
        Arrays.fill(dist, Constant.Max);
        dist[0] = 0;

        Arrays.fill(pPath, -1);
        pPath[0] = 0;

        int n = arrV.length;

        for (int k = 0; k < n; k++) {

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] != Constant.Max &&
                    dist[j] > dist[i] + matrix[i][j]) {
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != Constant.Max &&
                        dist[j] > dist[i] + matrix[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public void floydWarShall(int[][] dist, int[][]pPath) {
        int n = arrV.length;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Constant.Max);
            Arrays.fill(pPath[i], -1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != Constant.Max) {
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                } else {
                    if (i == j) {
                        dist[i][j] = 0;
                        pPath[i][j] = -1;
                    }
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Constant.Max && dist[k][j] != Constant.Max
                            && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        //更新路径节点下标
                        //pPath[i][j] = k;//不对
                        pPath[i][j] = pPath[k][j];
                    }
                }
            }
            //打印
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(dist[i][j] == Constant.Max) {
                        System.out.print(" * ");
                    }else{
                        System.out.print(dist[i][j]+" ");
                    }
                }
                System.out.println();
            }
            System.out.println("=========打印路径==========");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(pPath[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println("=================");
        }
    }
}
